package learn;

public class DivChessConquer {
    public static void main(String[] args) {
        int size = 4;
        int[][] board = new int[size][size];
        chessBoard(board, size, 0, 0, 0, 0);
        display(board, size);
    }

    private static int tile;

    private static void display(int[][] board, int size) {
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                System.out.print(board[i][j] + "\t");
            }
            System.out.println("");
        }
        System.out.println("");
    }

    /**
     * 分治法，每一次将棋盘一分为四
     *
     * @param board 棋盘
     * @param size  当前棋盘大小
     * @param tr    棋盘左上角的row
     * @param tc    棋盘左上角的column
     * @param dr    特殊方格的row
     * @param dc    特殊方格的column
     */
    private static void chessBoard(int[][] board, int size, int tr, int tc, int dr, int dc) {
        if (size <= 1) return;
        tile += 1;

        // 这一步非常细节，非常坑！不能直接使用全局变量tile来作为赋值
        // 因为之后的操作涉及到递归而且没有回溯tile的值！！
        // 所以全局变量tile会在我们预期之外增加
        int curTile = tile;
        size /= 2;  // 每一将棋盘一分为4，故size为原本的1/2

        // 棋盘划分为了4大部分
        if (dr < tr + size && dc < tc + size) { // 特殊方格在划分后棋盘的左上角
            chessBoard(board, size, tr, tc, dr, dc);
        } else {
            int conquerR = tr + size - 1, conquerC = tc + size - 1;
            board[conquerR][conquerC] = curTile;
            chessBoard(board, size, tr, tc, conquerR, conquerC);
        }
        if (dr < tr + size && dc >= tc + size) { // 特殊方格在划分后的右上角
            chessBoard(board, size, tr, tc + size, dr, dc);
        } else {
            int conquerR = tr + size - 1, conquerC = tc + size;
            board[conquerR][conquerC] = curTile;
            chessBoard(board, size, tr, tc + size, conquerR, conquerC);
        }
        if (dr >= tr + size && dc < tc + size) {    // 特殊方格在划分后的左下角
            chessBoard(board, size, tr + size, tc, dr, dc);
        } else {
            int conquerR = tr + size, conquerC = tc + size - 1;
            board[conquerR][conquerC] = curTile;
            chessBoard(board, size, tr + size, tc, conquerR, conquerC);
        }
        if (dr >= tr + size && dc >= tc + size) {   // 特殊方格在划分后的右下角
            chessBoard(board, size, tr + size, tc + size, dr, dc);
        } else {
            int conqerR = tr + size, conquerC = tc + size;
            board[conqerR][conquerC] = curTile;
            chessBoard(board, size, tr + size, tc + size, conqerR, conquerC);
        }
    }
}
